package zhengqc.list;

public class SinglyLinkedList<E> extends AbstractList<E> {
    private class Node {
        public E element;
        public Node next;
        public Node(E element, Node next) {
            this.element = element;
            this.next = next;
        }
        public Node(E element) {
            this(element, null);
        }
        public Node() {
            this(null, null);
        }
        @Override
        public String toString() {
            return element.toString();
        }
    }
    /* 单向链表头指针 */
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
        this.size = 0;
    }

    /* 获取单向链表 index 位置对应节点对象的引用 */
    private Node getNode(int index) {
        rangeCheck(index);
        Node node = this.head;
        for (int i = 0; i < index; ++i) {
            node = node.next;
        }
        return node;
    }

    /* 删除单链表中第一个值为 element 的元素 */
    public void removeElement(E element) {
        Node dummyHead = new Node(null, this.head);
        Node prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.element.equals(element)) {
                prev.next = prev.next.next;
                --this.size;
                break;
            } else {
                prev = prev.next;
            }
        }
        this.head = dummyHead.next;
        return;
    }

    /* 删除单链表中所有值为 element 的元素 */
    public void removeAllElements(E element) {
        Node dummyHead = new Node(null, this.head);
        Node prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.element.equals(element)) {
                prev.next = prev.next.next;
                -- this.size;
            } else {
                prev = prev.next;
            }
        }
        this.head = dummyHead.next;
        return;
    }
    /* 反转单链表 */
    public void reverse() {
        if (head == null || head.next == null) return;
        Node prev = null, current = this.head, next;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        this.head = prev;
    }
    @Override /* 获取单向链表指定元素的位置 */
    public int indexOf(E element) {
        Node current = head;
        for (int i = 0; current != null; ++i) {
            if (current.element.equals(element)) {
                return i;
            }
            current = current.next;
        }
        return ELEMENT_NOT_FOUND;
    }

    @Override /* 清空单向链表的所有元素 */
    public void clear() {
        this.size = 0;
        this.head = null;
    }

    @Override /* 在单向链表的 index 位置添加元素 element*/
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        if (index == 0) {
            this.head = new Node(element, this.head);
        } else {
            Node prev = getNode(index-1);
            prev.next = new Node(element, prev.next);
        }
        ++ this.size;
    }

    @Override /* 在单向链表开始位置添加元素 element*/
    public void addFirst(E element) {
        add(0, element);
    }

    @Override /* 在单向链表末尾位置添加元素 element*/
    public void addLast(E element) {
        add(this.size, element);
    }

    @Override /* 删除单向链表的 index 位置的元素 */
    public E remove(int index) {
        rangeCheck(index);
        Node node = head;
        if (index == 0) {
            this.head = this.head.next;
        } else {
            Node prev = getNode(index-1);
            node = prev.next;
            prev.next = node.next;
        }
        -- this.size;
        return node.element;
    }

    @Override /* 删除单向链表开始位置的元素 */
    public E removeFirst() {
        return remove(0);
    }

    @Override /* 删除单向链表末尾位置的元素 */
    public E removeLast() {
        return remove(this.size-1);
    }

    @Override /* 设置单向链表 index 位置的元素 */
    public void set(int index, E element) {
        getNode(index).element = element;
    }

    @Override /* 获取单向链表 index 位置的元素 */
    public E get(int index) {
        return getNode(index).element;
    }

    @Override /* 单向链表转数组 */
    public E[] toArray() {
        E[] array = (E[]) (new Object[this.size]);
        Node current = head;
        for (int i = 0; current != null; ++i) {
            array[i] = current.element;
            current = current.next;
        }
        return array;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("SinglyLinkedList: size=").append(this.size).append(", content=[");
        Node current = head;
        while (current != null) {
            sb.append(current.element.toString()).append("->");
            current = current.next;
        }
        sb.append("NULL]");
        return sb.toString();
    }
}
